# -*- encoding: utf-8 -*-
'''
Filename         :32_longestValidParentheses.py
Description      :
Time             :2022/08/23 16:51:04
Author           :daiyizheng
Email            :387942239@qq.com
Version          :1.0
'''

class Solution:
   # 用栈模拟一遍，将所有无法匹配的括号的位置全部置0
   # 例如: "()(()"的mark为[1, 1, 0, 1, 1]
   # 再例如: ")()((())"的mark为[0, 1, 1, 0, 1, 1, 1, 1]
   # 经过这样的处理后, 此题就变成了寻找最长的连续的1的长度
    def longestValidParentheses(self, s: str) -> int:
        stack = []
        mask = [0] * len(s)
        for i, c in enumerate(s):
            if c=="(":
                stack.append(i)
            else:
                if not len(stack):
                    continue
                else:
                    index = stack.pop()
                    mask[index] = 1
                    mask[i] = 1
        ## 找到做大长度1
        max_total =0
        total = 0
        for v in mask:
            if v:
                total += 1
            else:
                max_total = max(total, max_total)
                total = 0
        max_total = max(total, max_total)
        return max_total

if __name__ == '__main__':
    Solution().longestValidParentheses("(()")